//堆排序

#pragma once

//把a[s..m]调整为大顶堆
//假设除a[s]之外，其他元素都符合大项堆的定义
template <typename E>
void HeapAdjust(E a[] ,int s, int m)
{
    E tmp=a[s];
    for(int j =2*s+1;j<=m; j=2*s+1){ 
         if(j<m&&a[j+1]>a[j]) j++;
         if(a[j] <=tmp) break;
         a[s]=a[j];
         s=j;
    }
        a[s] =tmp;
}

//堆排序
template <typename E>
void HeapSort(E a[],int n){
    //建立大顶堆
    for(int i=(n-3)/2;i>=0; i--)
    HeapAdjust(a, i,n-1);
    //继续堆排序
    for(int i=n-1;i>0;i--) {
    std::swap(a[0] , a[i] );
    HeapAdjust(a, 0, i-1);
    }
    }